/*https://leetcode.cn/problems/climbing-stairs/submissions/562785946/
爬楼梯
24/9/6
*/

class Solution {
public:
    // 递归函数，计算爬到第 n 级台阶的方法数
    int climb(int n) {
        // 基本情况：如果 n 是 1、2 或 3，直接返回 n
        if (n == 1 || n == 2 || n == 3) {
            return n;
        }
        // 递归计算：返回爬到第 n-1 级和第 n-2 级台阶的方法数之和
        return climb(n - 1) + climb(n - 2);
    }

    // 主函数，计算爬到第 n 级台阶的方法数
    int climbStairs(int n) {
        // 调用递归函数计算方法数
        int result = climb(n);
        return result;
    }
};